#include <iostream>
#include <cstdlib>
#include <list>
#include <string>
#include <vector>

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

using std::pair;
using std::vector;
using std::string;

typedef int Status;
typedef pair<char, int> TElemType;
typedef struct HuffmanNode
{
	TElemType data;
	int weight;
	struct HuffmanNode *lchild, *rchild, *parent;
}HuffmanNode;														//哈夫曼结点

typedef struct{
	char ch;
	int weight;
	string code;
}inf;																//由字符、权值和哈夫曼编码构成的字符结点

class HuffmanTree
{
public:
	HuffmanNode *root;
	HuffmanTree();
	HuffmanTree(pair<char, int>);
	HuffmanTree(HuffmanTree lchild, HuffmanTree rchild);
	Status InitHuffmanTree();
	Status DestroyHuffmanTree();
	Status CreateHuffmanTree(void (*func)(HuffmanNode *T));
	Status ClearHuffmanTree(HuffmanNode *T);
	bool HuffmanTreeEmpty();
	int HuffmanTreeDepth(HuffmanNode *T, bool isroot);
	HuffmanNode *Root();	
	TElemType Value(HuffmanNode *e);
	int Weight();
	Status Assign(HuffmanNode *e, TElemType value);
	HuffmanNode *Parent(HuffmanNode *e);
	HuffmanNode *LeftChild(HuffmanNode *e);
	HuffmanNode *RightChild(HuffmanNode *e);
	HuffmanNode *LeftSibling(HuffmanNode *e);
	HuffmanNode *RightSibling(HuffmanNode *e);
	Status InsertChild(HuffmanNode *p, int LR, HuffmanNode *c);
	Status DeleteChild(HuffmanNode *p, int LR);
	Status PreOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T, bool isroot);
	Status InOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T, bool isroot);
	Status PostOrderTraverse(Status (*visit)(TElemType e), HuffmanNode *T, bool isroot);
	Status LevelOrderTraverse(Status (*visit)(TElemType e));
	void CreateDict(vector<inf> &dict, HuffmanNode *node, string code);
	int WeighedLength(HuffmanNode *node, int length);
};
